// https://leetcode.cn/problems/greatest-sum-divisible-by-three/description/

// 算法思路总结：
// 1. 贪心策略处理可被3整除的最大和问题
// 2. 统计总和并记录模3余1和余2的最小两个数
// 3. 根据总和余数选择最优删除方案
// 4. 比较删除一个余1数或两个余2数的结果
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    const int INF = 0x3f3f3f3f;
    int maxSumDivThree(vector<int>& nums) 
    {
        int m = nums.size();
        int sum = 0, x1 = INF, x2 = INF, y1 = INF, y2 = INF;

        for (const int& num : nums)
        {
            sum += num;
            if (num % 3 == 0)
            {
                continue;
            }
            else if (num % 3 == 1)
            {
                if (num < x1)
                {
                    x2 = x1;
                    x1 = num;
                }
                else if (num < x2)
                {
                    x2 = num;
                }
            }
            else if (num % 3 == 2)
            {
                if (num < y1)
                {
                    y2 = y1;
                    y1 = num;
                }
                else if (num < y2)
                {
                    y2 = num;
                }
            }
        }

        if (sum % 3 == 0)  
            return sum;
        else if (sum % 3 == 1)
            return max(sum - x1, sum - y1 - y2);
        else    
            return max(sum - y1, sum - x1 - x2);
    }
};

int main()
{
    vector<int> nums1 = {3,6,5,1,8}, nums2 = {1,2,3,4,4};
    Solution sol;

    cout << sol.maxSumDivThree(nums1) << endl;
    cout << sol.maxSumDivThree(nums2) << endl;

    return 0;
}